// 文件名：unordered_map_graph_adj.cpp
// 目的：使用邻接表（unordered_map<string, vector<string>）存储有向图，
//      并从给定起点执行广度优先搜索（BFS），以层序方式遍历节点。
// 要点：
//   - Graph 类型：哈希映射（节点ID -> 邻接列表），查找/插入平均 O(1)；
//   - 访问标记：unordered_set<string>，避免重复入队与死循环；
//   - 队列：deque<string> 作为 BFS 先进先出队列；
//   - graph.contains(start)：检查起点是否存在，防止非法访问；
//   - 对每个弹出的节点，查找其邻接列表并将未访问的邻居入队。
// 复杂度：
//   - 时间：O(V + E)（均摊哈希操作），空间：O(V)（队列与访问集）。
// 注意：
//   - 邻接表中缺失的节点默认视为出度为 0；
//   - 若图可能存在不连通分量，单次 BFS 仅遍历与起点连通的部分。

#include <deque>
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using Graph = std::unordered_map<std::string, std::vector<std::string>>;

void bfs(const Graph& graph, const std::string& start) {
    std::unordered_set<std::string> visited;
    std::deque<std::string> queue;

    if (!graph.contains(start)) {
        std::cout << "Start node missing.\n";
        return;
    }

    visited.insert(start);
    queue.push_back(start);

    std::cout << "BFS: ";
    while (!queue.empty()) {
        auto node = queue.front();
        queue.pop_front();
        std::cout << node << ' ';

        // 查找并遍历当前节点的邻接点
        if (auto it = graph.find(node); it != graph.end()) {
            for (const auto& neighbor : it->second) {
                if (!visited.contains(neighbor)) {
                    visited.insert(neighbor);
                    queue.push_back(neighbor);
                }
            }
        }
    }
    std::cout << '\n';
}

int main() {
    Graph graph = {
        {"A", {"B", "C"}},
        {"B", {"D", "E"}},
        {"C", {"F"}},
        {"E", {"F"}}
    };

    bfs(graph, "A"); // 正常起点
    bfs(graph, "Z"); // 缺失起点

    return 0;
}